package LimitedTimeGame.Day_0218;

/**
 * @author zxc
 * @date 2023/02/18 08:59
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：
 * 题目详述 ：
 * 给你一个函数f(x, y)和一个目标结果z，函数公式未知，请你计算方程f(x,y) == z所有可能的正整数数对x 和 y。
 * 满足条件的结果数对可以按任意顺序返回。
 * 尽管函数的具体式子未知，但它是单调递增函数，也就是说：
 * f(x, y) < f(x + 1, y)
 * f(x, y) < f(x, y + 1)
 *
 * 你的解决方案将按如下规则进行评判：
 *
 * 判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
 * 判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
 * 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
 * 如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。
 *
 * 提示：
 * 1 <= function_id <= 9
 * 1 <= z <= 100
 * 题目保证f(x, y) == z的解处于1 <= x, y <= 1000的范围内。
 * 在 1 <= x, y <= 1000的前提下，题目保证f(x, y)是一个32 位有符号整数。
 *
 */
public class FindSolution03 {
    /**
     * 思路 ：
     * 即，使用双指针来遍历所有可能的数对
     * ===》
     *  由于f(x, y) < f(x + 1, y) && f(x, y) < f(x, y + 1);
     *  即，若是x1 > x2,则f(x1 , y1) == f(x2 , y2) == z;
     *  由于y相同的情况下，f(x1 , y) > f(x2 , y); 即，为了保证f(x1 , y1) == f(x2 , y2) == z，则需要满足y1 < y2;
     *  ===>
     *  等价于，从小到大遍历所有可能的x（指针p1指向x ） && 从大到小遍历所有可能的y（指针p2指向y ）
     *  即，每次不需要对于y 从头开始重新进行遍历，而是直接当前指针p2指向的元素进行遍历即可;
     *
     * @param customfunction
     * @param z
     * @return
     */
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
        int p1 = 1;
        int p2 = 1000;
        while(p1 <= 1000){
            // 右指针左移条件 ：右指针指向的元素不为空 && 当前f(p1,p2)值 >= z;
            // 为啥当前f(p1,p2)值 >= z
            // ===》 由于固定住p1值的前提下，即f(p1,y)是单调递增函数，若是y递减的话，则代表了f(p1,y)值也在递减;
            while(p2 > 0 && customfunction.f(p1 , p2) >= z){
                if(customfunction.f(p1 , p2) == z){
                    List<Integer> list = new ArrayList<>();
                    list.add(p1);
                    list.add(p2);
                    result.add(list);
                    p2--;
                    break;
                }
               p2--;
            }
            p1++;
        }
        return result;
    }
    interface CustomFunction {
        // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
        int f(int x, int y);
    };
}
